package leetcode_1001_1100;

import node.ListNode;

import java.util.*;

public class LeeCode_1019 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextLargerNodes(new ListNode(2, new ListNode(1, new ListNode(5))))));
    }
    private static int[] nextLargerNodes(ListNode head) {
        List<Integer> nums = new ArrayList<>();
        while (head != null){
            nums.add(head.val);
            head = head.next;
        }
        Deque<Integer> stk = new ArrayDeque<>();
        int n = nums.size();
        int[] ans = new int[n];
        for(int i = n - 1; i >= 0; i--){
            while (!stk.isEmpty() && stk.peek() <= nums.get(i)){
                stk.pop();
            }
            if (!stk.isEmpty())
                ans[i] = stk.peek();
            stk.push(nums.get(i));
        }
        return ans;
    }
}
